package old.steiner;

import java.util.ArrayList;
import java.util.Arrays;

import old.pso.FitnessEvaluator;
import old.pso.Particle;




import basic.Point;

import disjointset.DisjointSet;
import disjointset.Node;

public class BottleneckEvaluator extends DisjointSet implements FitnessEvaluator {
	
	private ResettableNode[] nodes;
	private Edge[] edges;
	private int k;
	private int steps;
	private double minimalBottleneck;
	private double maxSqLength;
	
	public BottleneckEvaluator(STP problem) {
		this.nodes = convert(problem.getPoints());
		this.k = problem.getK();
		specialKruskall();
	}
	
	private ResettableNode[] convert(Point[] points) {
		int n = points.length;
		ResettableNode[] nodes = new ResettableNode[n];
		for(int i=0;i<n;i++) {
			nodes[i] = new ResettableNode(points[i]);
		}
		return nodes;
	}
	
	/**
	 * This method creates subtrees according to the algorithm of kruskall
	 * until the (n-1-4*k)th step.
	 * At this step it creates the reset point and starts adding the remaining edges
	 * to the edges to be used when processing a particle.
	 */
	private void specialKruskall() {
		int n = nodes.length;
		steps = Math.max(0, n-1-4*k);
		edges = new Edge[n-1-steps];
		Edge[] allEdges = getAllEdges(nodes);
		int i = 0;
		for(Edge edge : allEdges) {
			if(noLoops(edge)) {
				if(i == steps-1) {
					minimalBottleneck = edge.getLength();
				}
				if(i == steps) {
					setResetpoint();
				}
				super.union(edge.getA(),edge.getB());
				if(i >= steps) {
					edges[i-steps] = edge;
				}
				if(i == (n-1)-1) {
					maxSqLength = edge.getSquaredLength();
					break;
				}
				i++;
			}
		}
		reset();
	}
	
	private void setResetpoint() {
		for (ResettableNode node : nodes) {
			node.setResetPoint();
		}
	}

	/**
	 * Reset the nodes to the topology of subsets after the (n-1-4k)th step in kruskall.
	 */
	private void reset() {
		for(ResettableNode node : nodes) {
			node.reset();
		}
	}
	
	/**
	 * Checks that this edge can be added to the forest without creating loops.
	 */
	private boolean noLoops(Edge edge) {
		return super.find(edge.getA()) != super.find(edge.getB());
	}
	
	private Edge[] getAllEdges(Node[] nodes) {
		int n = nodes.length;
		// a complete graph has n nodes and n*(n-1)/2 edges
		int nbOfAllEdges = n * (n-1) / 2;
		Edge[] allEdges = new Edge[nbOfAllEdges];
		
		int nbOfEdges = 0;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++) {
				allEdges[nbOfEdges++] = new Edge(nodes[i],nodes[j]);
			}
		}
		Arrays.sort(allEdges);
		return allEdges;
	}

	@Override
	public double getFitness(Particle particle) {
		Edge[] edges = getEdges(particle);
		double result = minimalBottleneck;
		int nbOfNewEdges = nodes.length-1 + k - steps;
		boolean complete = false;
		for(Edge edge: edges) {
			if(noLoops(edge)) {
				union(edge.getA(),edge.getB());
				if(--nbOfNewEdges == 0) {
					result = edge.getLength();
					complete = true;
					break;
				}
			}
		}
		reset();
		return complete? result : Double.MAX_VALUE;
	}
	
	/**
	 * Returns a sorted array of all the new edges introduced by the steiner points
	 * + the old longest edges of the MST.
	 */
	private Edge[] getEdges(Particle particle) {
		Node[] steinernodes = getSteinerNodes(particle);
		
		Edge[] extraEdges = getSteinerEdges(steinernodes);
		
		// Merges the edges of the MST and the edges introduced by the steiner points
		// in 1 sorted array.
		Edge[] allEdges = merge(edges,extraEdges);
		
		Arrays.sort(allEdges);
		return allEdges;
	}
	
	private <T> T[] merge(T[] a, T[] b) {
		T[] c = Arrays.copyOf(a, a.length + b.length);
		System.arraycopy(b, 0, c, a.length, b.length);
		return c;
	}
	
	/**
	 * Convert the particle to an array of k steiner nodes.
	 */
	private Node[] getSteinerNodes(Particle particle) {
		Node[] steinerNodes = new Node[k];
		int j = 0;
		for (int i=0; i<k;i++) {
			steinerNodes[i] = new Node(particle.position[j++],particle.position[j++]);
		}
		return steinerNodes;
	}

	/**
	 * Generate all new edges generated by the added steiner points.
	 */
	private Edge[] getSteinerEdges(Node[] steinernodes) {
		ArrayList<Edge> allEdges = new ArrayList<Edge>();
		for(int i=0;i<k;i++) {
			for(int j=i+1;j<k;j++){
				Edge edge = new Edge(steinernodes[i],steinernodes[j]);
				if(edge.getSquaredLength() < maxSqLength) {
					allEdges.add(edge);
				}
			}
			for(int j=0;j<nodes.length;j++) {
				Edge edge = new Edge(steinernodes[i],nodes[j]);
				if(edge.getSquaredLength() < maxSqLength) {
					allEdges.add(edge);
				}
			}
		}
		Edge[] result = new Edge[allEdges.size()];
		return allEdges.toArray(result);
	}
	
}
